The present invention is directed to texture mapping in computer graphics. It specifically concerns the manner in which a texture image is stored for use in texture mapping.
A situation commonly encountered in computer graphics is the need to render an image of an object whose surface has a detailed pattern. The surface's image is computed from digital samples of the pattern itself. That stored pattern image is known as a texture map.
Despite the name, a texture map is not limited to perturbations in surface normals; for instance, the "texture" image that it represents can be a color pattern, such as a plaid pattern in two-space, that "wallpapers" the surface of an object whose image is being computed.
FIG. 1 depicts in simplified form a typical system 10 for generating images of objects that have been defined by any of the many types of object descriptions ordinarily employed for this purpose. For example, in FIG. 2's object surface 11 may be represented as, say, a plurality of bicubic patches defined by parametric equations. That is, one way to define a surface segment is to use three-space parametric equations such as: EQU x=(a.sub.x3 s.sup.3 +a.sub.x2 s.sup.2 +a.sub.x1 s+a.sub.x0)(b.sub.x3 t.sup.3 +b.sub.x2 t.sup.2 +b.sub.x1 t+b.sub.x0) EQU y=(a.sub.y3 s.sup.3 +a.sub.y2 s.sup.2 +a.sub.y1 s+a.sub.y0)(b.sub.y3 t.sup.3 +b.sub.y2 t.sup.2 +b.sub.y1 t+b.sub.y0) EQU z=(a.sub.z3 s.sup.3 +a.sub.z2 s.sup.2 +a.sub.z1 s+a.sub.z0)(b.sub.z3 t.sup.3 +b.sub.z2 t.sup.2 +b.sub.z1 t+b.sub.z0),
where (x, y, z) is a location in three space, s and t are parameters that range, say, from 0 to 1 for all patches, and the a's and the b's are the stored coefficients that form the patch description. Of course, this is only one of the many object-description methods known to those skilled in the art.
To render the image, a scan-conversion process 12 in FIG. 1's output-image generator 13 converts this description into corresponding scan locations addressed by a picture-element ("pixel")-address calculator 14, and a pixel-value calculator 15 computes each pixel value drawn by a display system 16's display circuitry 17 to drive its display device 18, such as a computer monitor or printer. The scan-conversion process typically treats the display pixel as a small rectangle 19 (FIG. 2) in an object-space display plane, and it projects that rectangle onto the surface 11. This gives the location on the surface but not, say, its color. The pixel-value calculator 15 obtains the color from a texture image with which process 12 has "papered" the surface, mapping the surface into a is (typically but not necessarily two-dimensional) texture space 20.
Data in a texture memory 21 (FIG. 1) represent the texture image as values of texture elements ("texels") thereof just as the pixel-value calculator 15 represents the displayed image as values of output-image pixels. The texel values can be thought of as samples from a texture image that is continuous in, say, a two-dimensional (u, v) texture space. The mapping of the output pixel 19's projection 22 into the texture space defines an area 23 that may encompass a number of texels. If so, all of those texels' values need to be taken into account in order to produce an accurate pixel value. To compute the pixel value, the pixel-value calculator 15 may simply average all of those texel values, possibly after weighting some in accordance with the fraction of the associated texel that falls within the area 23. In other cases, more-complicated filtering may be employed. In any event, pixel-value computation requires that those texel values be located and fetched from the texture memory 20. This is the function of a texture-address-calculation circuit 24, which will be described presently.
Now, the need to fetch a plurality of texel values for each pixel-value computation can become onerous, as FIG. 3 illustrates. FIG. 3 depicts the object space and includes an edge view of the image plane 32. Tick marks 34 represent assumed pixel boundaries, and an eye 36 represents the viewpoint in accordance with which the object image is to be determined.
We assume that the texture image is to cover two planar surfaces 38 and 40. The projection of one pixel onto plane 38 is shown to cover approximately 4.times.4=16 texels. Fetching this many values for a single pixel is onerous enough, but plane 40 shows that the problem can become considerably worse.
To reduce this problem, the texture memory may store a texture image as a plurality of texture maps, each of which represents the texture image with a different resolution. A base pixel map represents the texture image as values of a large number of small texels. Pre-filtering the base texture map produces texture maps that express the texture image as the values of increasingly small numbers of increasingly large texels. Typically, although not necessarily, each successive texture map of a set consists of the values of texels whose linear dimensions are half those of the previous texture map's texels. These pre-filtered maps are often referred to as "mip maps." When the output-image generator 13 then requests texture data for use in calculating a given pixel value, it does so by way of an ordered triple (u, v, d), where u and v are spatial coordinates in the texture space and d is an indication of the spatial resolution with which the data should be represented. Generator 13 typically expresses u and v with sub-texel resolution. Similarly, it computes the quantity d as a continuous function of, say, the partial derivatives of the texture-space coordinates with respect to the display-space coordinates, and the result typically falls between d values that correspond to respective maps. From these values, the texture-address-calculation circuit 24 determines which texture maps and constituent locations contain the needed texel data.
Texels of more than one resolution may be required for a single pixel-value computation, so it is important that texture-memory accesses be performed rapidly even if data for a given pixel-value computation must be drawn from different maps. FIG. depicts a memory organization typically used in attempting to achieve this result. FIG. 4 treats the texture-memory address space as two-dimensional: the vertical position in FIG. 4 represents the value of certain of the address bits, and horizontal position in that drawing represents the value of the remainder. If the texture maps are stored in DRAM devices, for example, the vertical and horizontal positions may respectively represent the values of the row and column addresses sequentially applied to those devices.
The memory's largest segment 42, whose row- and column-address values are both at least twice those in any other segment, contains the base, finest-spatial-resolution texture map. FIG. 4 depicts the upper left corner of that segment as corresponding to the (u, v) origin, with u and v increasing with increasing column and row addresses, respectively. This map corresponds to, say, d=0. Another segment 44 represents the same image with the same range in (u, v), but the spatial sampling resolution is coarser by a factor of 2. This map may correspond to d=1. Segments 46 and 48 are successively coarser texture maps which may respectively correspond to d=2 and d=3. A final segment 50 is conventionally left empty.
This organization is more typically depicted as in FIG. 5, which shows its use for the three sets of texture maps required for a color texture image: segment 51 contains the highest-spatial-resolution red-component texel information, segment 52 contains highest-spatial-resolution green-component information, and segment 54 contains the highest-spatial-resolution blue texel information.
The memory organization of FIGS. 4 and 5 is considered advantageous for multiple-resolution texel-data retrieval because addresses for texel data in different maps corresponding to the same locations in texture space are simply shifted versions of one another. If segment 42 is an (atypically small) 8.times.8-location memory segment, for instance, then its lower-right location's binary address is (0111, 1111), while segment 42's lower-right location's address is (0011, 01 11), and that of segment 46 is (0001, 0011).